package 纯数组;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

public class JZ39数组中出现次数超过一半的数字 {

    /**
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     *
     * 示例 1:
     * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
     * 输出: 2
     *  
     * 限制：
     * 1 <= 数组长度 <= 50000
     */

    /**
     * 最优解法是 摩尔投票法,正负票数抵消
     */
    public int goodMethod(int[] nums) {

        int num=-1;
        int count=0;

        for (int i : nums) {
            if(count==0){
                num=i;
            }
            if(i==num){
                count++;
            }else{
                count--;
            }
        }
        return num;
    }

    public int majorityElement(int[] nums) {
        if(nums.length<1){
            return -1;
        }
        Map<Integer,Integer> map=new HashMap<>();
        int maxCount=0;
        int result=0;
        for (int i = 0; i < nums.length; i++) {
            Integer integer=map.get(nums[i]);
            int thisCount=integer==null?0:integer;
            map.put(nums[i],thisCount+1);
            if(thisCount+1>maxCount){
                maxCount=thisCount+1;
                result=nums[i];
            }
        }
        return result;
    }


}
